As a form of networks including a plurality of node apparatuses, the ad-hoc network has been put to practical use. In the ad-hoc network, an autonomous path selection is performed in each node apparatus. That is, each node apparatus in the ad-hoc network has a function to operate as a router or a switch. Here, each node apparatus is able to recognize the surrounding network configuration by sending and receiving a message and the like to and from adjacent node apparatuses. Therefore, by adopting the ad-hoc (especially, wireless ad-hoc) scheme, a desired network may be established just by placing node apparatuses in an environment in which establishment of the network is desired, without providing a network management system that manages the network. Furthermore, in the ad-hoc network, addition or elimination of the node apparatus is easy, and the network configuration can be changed easily. Meanwhile, conventionally a wireless communication system in which the connection may be updated by adding a new node apparatus that is not on the path, without establishing the path again has been proposed (for example, Japanese Laid-open Patent Publication No. 2006-135482).
It is preferable that the network has an alternative path (or a redundant path or a detour path) so that even when a failure occurs, the communication may be continued. Especially in the wireless network, a link may be temporarily disconnected due to the radio wave environment, and it is important to check the presence/absence of an alternative path in advance. For this reason, a technique to recover from the failure by a distributed-type automatic bypass routing upon a link failure in a network including a plurality of node apparatuses has been proposed (for example, Japanese Laid-open Patent Publication No. 3-117140).
However, in the ad-hoc network, it is difficult to recognize the communication path across entire network. Therefore, in the ad-hoc network, it is not easy to recognize whether or not an alternative path exists for each communication path.